class KjedaListe<T> implements ListeADT<T> {
// Klasse for ordna liste implementert med kjeda struktur Kap. 8.5
//
    protected int antal;
    protected LinearNode<T> første, siste;

    public KjedaListe(){
        antal = 0;
        første = null; siste = null;
    }

    public T fjernFørste(){
        T svar = null;
        if(!erTom()){
            svar = første.hentElement();
            første = første.hentNeste();
            antal--;
        }
        return svar;
    }
    public T fjernSiste(){
        T svar = null;
        if(!erTom()){
            svar = siste.hentElement();
            antal--;
            if (antal==0){
            	første=null; siste=null;
            }else{
            	siste=første;
            	for(int i = 1; i<antal; i++)
            		siste = siste.hentNeste();
            	siste.settNeste(null);
            }
        }
        return svar;
    }
    public T fjern(T element){
    //Søk etter og fjern gitt element (generell, uordna liste)
    
        T svar = null;
        LinearNode<T> forrige=null, denne=første;
        while(denne!=null && 
        		!element.equals(denne.hentElement())){
        	forrige=denne; denne = denne.hentNeste();
        }
        if(denne!=null){
        	antal--;
        	svar = denne.hentElement();	
        	if(forrige == null){	//Første element
        		første = første.hentNeste();
        		if(første==null) 	//Tom liste
        			siste=null;
        	}else{
        		forrige.settNeste(denne.hentNeste());
        		if(denne==siste){
        			siste=forrige;
        		}
        	}
        }
        return svar;
    }
    
    public T første(){
        T svar = null;
        if(!erTom()){
            svar = første.hentElement();
        }
        return svar;
    }
    public T siste(){
        T svar = null;
        if(!erTom()){
            svar = siste.hentElement();
        }
        return svar;
    }
    public boolean inneholder(T element){
        LinearNode denne=første;
        while(denne!=null && 
        		!element.equals(denne.hentElement())){
        	denne = denne.hentNeste();
        }
        return (denne!=null);
    }
    
    public KjedetIterator<T> iterator (){
    	return new KjedetIterator<T>(første, antal);
    } 
    public boolean erTom(){
        return antal == 0;
    }
    public int antall(){
        return antal;
    }
    
    /******************************************************************
     Returnerer en strengrepresentasjon av elementene i køen.. 
   ******************************************************************/
   public String toString(){
      String resultat = "" ;
      LinearNode<T> aktuell = første;

      while (aktuell != null)
      {
         resultat= resultat + (aktuell.hentElement()).toString() + "\t";
         aktuell = aktuell.hentNeste();
      }

      return resultat;
   }
      
}//class